package com.exercises;


import com.exercises.common.ListNode;

import java.util.Stack;

class Exercise92 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode current = head;
        for (int i = 2; i <= 5; i++) {
            ListNode node = new ListNode(i);
            current.next = node;
            current = current.next;
        }
        ListNode result = new Exercise92().reverseBetween(head, 2, 4);
        while (result != null) {
            System.out.println(result.val);
            result = result.next;
        }
    }


    public ListNode reverseBetween(ListNode head, int left, int right) {
        Stack<ListNode> stack = new Stack<>();
        ListNode current = head;
        for (int i = 1; i <= right; i++) {
            stack.push(current);
            current = current.next;
        }

        ListNode node = stack.pop();
        ListNode reverLeft = node, reverRight = node;
        for (int i = left; i < right; i++) {
            node.next = stack.pop();
            node = node.next;
        }
        node.next = current;
        if (stack.size() > 0) {
            stack.pop().next = reverLeft;
            return head;
        } else {
            return reverLeft;
        }

    }

}

